Recursion Tree Method

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Recursion #◇Recursion and Iteration #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

The Recursion Tree Method is a visual technique for solving recurrences by drawing the recursive calls as a tree and summing costs at each level.

◇Key Concepts

Visualizing recursive calls as a tree Summing costs level by level Determining tree depth and number of leaves Often used to "guess" the solution, then verify with the ◇Substitution Method

◇Details / Theory

How It Works

1. Draw the recursion tree — each node represents the cost of a single recursive call (excluding its children’s costs).
2. Determine cost per level — sum all node costs at each depth level.
3. Count the number of levels — the tree has depth $\log_b n$ for a recurrence that divides by $b$.
4. Sum across all levels to get the total cost $T(n)$.

Worked Example: $T(n) = 2T(n/2) + n$

Per-Level Cost Accounting:

• Level 0: 1 node with cost $cn$ $\implies$ Total = $cn$
• Level 1: 2 nodes, each with cost $c(n/2)$ $\implies$ Total = $cn$
• Level 2: 4 nodes, each with cost $c(n/4)$ $\implies$ Total = $cn$
• Level $k$: $2^k$ nodes, each with cost $c(n/2^k)$ $\implies$ Total = $cn$

Depth: The tree has $\log_2 n$ levels (since the input size halves at each recursive descent).
Leaves: At level $\log_2 n$, there are $2^{\log_2 n} = n$ base-case leaves, each with cost $\Theta(1)$, contributing $\Theta(n)$.

Total Cost Summation:
$T(n) = \sum_{k=0}^{\log_2 n - 1} cn + \Theta(n) = cn \log_2 n + \Theta(n) = \Theta(n \log n)$

Recurrence Tree Taxonomy & Behavior

Worked Example: $T(n) = 3T(n/4) + cn^2$

• Level 0: cost $cn^2$
• Level 1: 3 nodes, each cost $c(n/4)^2 = cn^2/16$ $\implies$ Total = $\frac{3}{16} cn^2$
• Level 2: 9 nodes, each cost $c(n/16)^2$ $\implies$ Total = $\left(\frac{3}{16}\right)^2 cn^2$
• Level $k$: Total cost = $\left(\frac{3}{16}\right)^k cn^2$

This is a strictly decreasing geometric series with common ratio $r = 3/16 < 1$. Sum of infinite geometric series yields:
$T(n) \le cn^2 \sum_{k=0}^{\infty} \left(\frac{3}{16}\right)^k = cn^2 \cdot \frac{1}{1 - 3/16} = \frac{16}{13} cn^2 = O(n^2)$

The root level dominates (top-heavy tree) — directly consistent with Master Theorem Case 3.

When to Use This Method

When you want a visual/intuitive understanding of the recurrence. To generate a "guess" for the ◇Substitution Method. When the ◇Master Theorem doesn’t directly apply.

◇Common Pitfalls

Forgetting to account for the cost at the leaf level. Incorrectly computing the number of nodes per level (it multiplies by $a$ each level, not $b$). Not recognizing geometric series patterns when summing across levels.

◇Summary

TL;DR — The Recursion Tree Method draws out recursive calls as a tree, sums costs per level, and totals them to solve the recurrence. It’s especially useful for intuition and as a precursor to formal proofs.

◇Links

Related: ◇Master Theorem — ◇Substitution Method — ◇Divide and Conquer — ◇Asymptotic Notation — ◇Recursion Source / Reference: Handout 03

◇References & Navigation

• Previous Topic: ◇Recurrences
• Next Topic: ◇Running Time
• Related Notes: ◇Algorithm Analysis, ◇Core Concepts